﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BinaryTreeCode
{
    class AttriOfTree
    {
        //=================================力扣404 左叶子之和
        //计算给定二叉树的所有左叶子之和
        //左叶子：如果左节点不为空，且左节点没有左右孩子，那个这个左节点就是左叶子
        //       判断当前节点是不是左叶子是无法判断的，必须通过节点的父节点来判断其左孩子是不是左叶子
        public int SumOfLeftLeaves(TreeNode root)
        {//递归法
            if (root == null)
                return 0;

            int leftValue = SumOfLeftLeaves(root.left);//左
            int rightValue = SumOfLeftLeaves(root.right);//右

            int midValue = 0;                           //中
            if (root.left != null && root.left.left == null && root.left.right == null)
                midValue = root.left.val;

            int sum = midValue + leftValue + rightValue;
            return sum;
        }
        public int SumOfLeftLeaves_2(TreeNode root)
        {//迭代法
            Stack<TreeNode> st = new Stack<TreeNode>();
            if (root != null)
                st.Push(root);
            int result = 0;
            while(st.Count > 0)
            {
                TreeNode node = st.Pop();

                if (node.left != null && node.left.left == null && node.left.right == null)
                    result += node.left.val;

                if (node.right != null)
                    st.Push(node.right);
                if (node.left != null)
                    st.Push(node.left);
            }
            return result;
        }


        //=========================================力扣513 找树左下角的值
        //给定一个二叉树的根节点，请找出该二叉树的最底层最左边节点的值
        //假设二叉树中至少有一个节点
        int maxLen = int.MinValue;//记录最大深度
        int maxLeftValue;            //记录最大深度时最左节点的值
        public int FindBootomLeftValue(TreeNode root)
        {//递归法
            //
            Traverssal(root, 0);
            return maxLeftValue;

        }
        void Traverssal(TreeNode root, int leftLen)
        {
            if(root.left == null && root.right == null)
            {//结束递归
                if(leftLen > maxLen)
                {
                    maxLen = leftLen;
                    maxLeftValue = root.val;//最大深度最左边的数值
                }
                return;
            }

            if(root.left != null)
            {
                leftLen++;//深度+1
                Traverssal(root.left, leftLen);
                leftLen--;//回溯，深度-1
            }
            if(root.right != null)
            {
                leftLen++;
                Traverssal(root.right, leftLen);
                leftLen--;
            }
            return;
        }

        public int FindBootomLeftValue_2(TreeNode root)
        {//迭代法
            Queue<TreeNode> que = new Queue<TreeNode>();
            if (root != null)
                que.Enqueue(root);
            int result = 0;
            while (que.Count > 0)
            {
                int size = que.Count;
                for (int i = 0; i < size; i++)
                {
                    TreeNode node = que.Dequeue();
                    if (i == 0)
                        result = node.val;//记录最后一行的第一个元素
                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                }
            }
            return result;
        }

        //=====================================力扣112 路径总和
        //给你一个二叉树的根节点root和一个表示目标和的整数targetSUm，
        //判断该树中是否存在根节点到叶子节点的路径，这条路径上的所有节点值相加等于目标和targetSum
        //叶子节点指的是没有子节点的节点
        //思路:我们要遍历从根节点到叶子的路径，看看总和是不是目标值
        public bool HasPathSum(TreeNode root, int targetSum)
        {//递归法
            if (root == null)
                return false;
            return Traversal(root, targetSum - root.val);
        }
        bool Traversal(TreeNode cur, int count)
        {//使用计数器递减的方法，让count初始为目标值，每次减去遍历节点的值，如果count==0且当前为叶子节点，说明找到了目标
            if (cur.left == null && cur.right == null && count == 0)
                return true;//遇到叶子节点且计数为0
            if (cur.left == null && cur.right == null)
                return false;//遇到叶子节点但计数不为0

            if(cur.left != null)
            {//左  空节点不遍历
                count -= cur.left.val;
                if (Traversal(cur.left, count))
                    return true;//这里有回溯的逻辑
                count += cur.left.val;
            }
            if(cur.right != null)
            {//左  空节点不遍历
                count -= cur.right.val;
                if (Traversal(cur.right, count - cur.right.val))
                    return true;//这里有回溯的逻辑
                count += cur.right.val;
            }
            return false;
        }

        public bool HasPathSum_2(TreeNode root, int targetSum)
        {//迭代法
            if (root == null)
                return false;
            Stack<TreeNode> stTree = new Stack<TreeNode>();
            Stack<int> stVal = new Stack<int>();
            stTree.Push(root);
            stVal.Push(root.val);
            while(stTree.Count > 0)
            {
                int size = stTree.Count;
                for(int i = 0;i<size;i++)
                {
                    TreeNode node = stTree.Pop();
                    int sum = stVal.Pop();

                    //如果是叶子节点且路径数值等于目标值则返回true
                    if (node.left == null && node.right == null && targetSum == sum)
                        return true;
                    if(node.right != null)
                    {//压入右节点，同时记录节点值
                        stTree.Push(node.right);
                        stVal.Push(sum + node.right.val);
                    }
                    if(node.left != null)
                    {//压入左节点，同时记录节点值
                        stTree.Push(node.left);
                        stVal.Push(sum + node.left.val);
                    }
                }
            }
            return false;
        }

        //==================================================力扣113 路径总和2
        //给定二叉树的根节点和一个整数目标和targetSum，找出所有从根节点到叶子节点路径综合等于给定目标和的路径
        List<IList<int>> result;
        List<int> path;
        public IList<IList<int>> PathSum(TreeNode root, int targetSum)
        {
            result = new List<IList<int>>();
            path = new List<int>();
            if (root == null)
                return result;
            path.Add(root.val);
            Traversal_2(root, targetSum - root.val);
            return result;
        }
        //递归函数不需要返回值，因为我们要遍历整个树
        void Traversal_2(TreeNode cur, int count)
        {
            if(cur.left == null && cur.right == null && count == 0)
            {//遇到叶子节点，且找到了和为目标值的路径
                result.Add(new List<int>(path));
                return;
            }
            if (cur.left == null && cur.right == null)
                return;//遇到叶子节点，但没找到合适的路径，直接返回

            if(cur.left != null)
            {//左 空节点不遍历
                path.Add(cur.left.val);
                count -= cur.left.val;
                Traversal_2(cur.left, count);//递归
                count += cur.left.val;//回溯
                path.RemoveAt(path.Count - 1);//回溯
            }
            if(cur.right != null)
            {//右
                path.Add(cur.right.val);
                count -= cur.right.val;
                Traversal_2(cur.right, count);//递归
                count += cur.right.val;//回溯
                path.RemoveAt(path.Count - 1);//回溯
            }
            return;
        }


    }
}
